更新时间:2023-06-01 21:25
Look-and-say 数列是数学中的一种数列,它的名字就是它的推导方式:给定第一项之后,后一项是前一项的发音。
1983年11月,在英国剑桥大学教书的著名数学家约翰·霍顿·康威(John Horton Conway) 首先发现了Look-and-say的奥秘。
如果我们把 1 作为Look-and-say 数列的第一项,那么,它的前几项是这样的:
1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211, ...
在确定了Look-and-say 数列的第一项之后,就可以根据前一项确定后一项的值了,在上面的示例中,我们把 1 作为此种数列的第一项,那么,就可以这样来推导它的其余项了:
第1个是 1 时,记作 1;
...
依此类推。
英国数学家约翰·康威(John Conway) 最早介绍和分析了Look-and-say 数列。
Look-and-say 数列和压缩/解压缩种的游标编码(Run-length encoding)有相似之处。
如果我们从0到9 中的任何数字d开始,那么d将永远是序列的最后一个数字。d不同于1,数列的开始几项如下:
d, 1d, 111d, 311d, 13211d, 111312211d, 31131122211d, …
巴黎综合理工学院的Ilan Vardi率先研究了 d =3 的状况, 约翰·康威(John Conway) 研究了 d=2 的情况,得出了康威常数。
增长性
当 d =22 时,很尴尬的事情发生了,Look-and-say 数列的前几项是:
22, 22, 22, 22,22, …
d 不等于 22 时,Look-and-say 数列可无限增长,也就是说可有无限个项。
数字出现的局限性
序列的各个项中,仅包含种子数字(上面提到的 d) 的各个数位上的阿拉伯数字 和 1,2 ,3 这三个阿拉伯数字。
宇宙衰变
康威的宇宙学定理断言,每一个序列最终都将(“衰变”)分裂成一系列的“原子元素”,它们是有限的子序列,不再与它们的邻居相互作用。有92个元素,其中只有1、2和3个数字,约翰·康威以铀元素命名,称这个序列为audioactive。还有两个“超铀元素”元素,分别是1、2和3。
增长率
在Look-and-say 数列 中,如果 表示数列的第n个成员的位数,那么存在比值极限
λ ≈ 1.303577269034...
这个事实由康威首先证明, 这个常数就被称为康威常数,常用 λ 表示。除了种子数字为 22 的Look-and-say 数列,其它此类数列均存在这个极限值。
康威常数λ 作为斜率换算为角度后,大约为 52.5075度。
康威常数还是一个 71次方多项式的唯一解。
图1x轴为种子数(22除外),y轴为10的n次方,
y的变化曲线的颜色代表了不同的种子数:23(红色)、1(蓝色)、13(紫色)、312(绿色)。这些曲线随着项数的增加趋向于直线,其斜率与康威常数一致。
几乎每种编程语言都可实现这个数列,这里给出一个 Go 语言的实现。